package com.fr.lintcode;

public class Q599 {
    /**
     * @param node:
     *            a list node in the list
     * @param x:
     *            An integer
     * @return: the inserted new list node
     */
    public ListNode insert(ListNode node, int x) {
        // write your code here
        ListNode insert = new ListNode(x);
        if (node == null) {
            insert.next = insert;
            return insert;
        }

        if (node.next == node) {
            node.next = insert;
            insert.next = node;
            return node;
        }
        ListNode min = null;
        ListNode max = null;
        ListNode t = node.next;
        while (t != node) {
            if (min == null || t.val < min.val) {
                min = t;
            }
            if (max == null || t.val > max.val) {
                max = t;
            }
            t = t.next;
        }
        if (min.val == max.val) {
            insert.next = node.next;
            node.next = insert;
            return node;
        }
        while (true) {
            // 中值
            if (node.val <= x && node.next.val >= x) {
                break;
            }
            // 最小值
            if (node.val > node.next.val && node.next.val > x && node.next.val == min.val) {
                break;
            }
            // 最大值
            if (node.val == max.val && node.next.val < node.val && node.val < x) {
                break;
            }
            node = node.next;
        }
        insert.next = node.next;
        node.next = insert;
        return node;

    }
}
